package bTree.LeetCode;

public class 矩阵中移动的最大次数 {
    public int maxMoves(int[][] grid) {
        int row = grid.length;
        int line = grid[0].length;
        int res=0;
        int [][]dp=new int[row][line];
        //让第一列都为1，其余为0，那么过不去的都为0，并且第一列为1的话第二列不会影响
        for (int i = 0; i < row; i++) {
            dp[i][0]=1;
        }
        for (int i=1;i<line;i++){
            for (int j=0;j<row;j++){
                int top=j-1;
                int mid=j;
                int bottom=j+1;
                if (top>=0&&dp[top][i-1]!=0&&grid[top][i-1]<grid[j][i]){
                    dp[j][i]=Math.max(dp[j][i],dp[top][i-1]+1);
                }
                if (dp[mid][i-1]!=0&&grid[mid][i-1]<grid[j][i]){
                    dp[j][i]=Math.max(dp[j][i],dp[mid][i-1]+1);
                }
                if (bottom<row&&dp[bottom][i-1]!=0&&grid[bottom][i-1]<grid[j][i]){
                    dp[j][i]=Math.max(dp[j][i],dp[bottom][i-1]+1);
                }
                res=Math.max(res, dp[j][i]);
            }
        }
        return res==0?0:res-1;
    }
}